// https://www.lintcode.com/problem/repeated-string-match/

public class Solution {
    /**
     * @param A: a string
     * @param B: a string
     * @return: return an integer
     */
    public int repeatedStringMatch(String A, String B) {
        // write your code here
        /*
        因为存在不匹配的可能性，要确定一个次数上限。
        如果A的长度是5，B的长度是15/16,那么最多循环4次一定就能匹配，否则无解。
        具体解释（能匹配的情况）：
        - A的格式：ABCDE
        - B的格式：EABCD-EABCD-EABCD-E
        - A循环4次：ABCD-[EABCD-EABCD-EABCD-E]
        - 但是如果B的长度是17，那么最多循环5次一定就能匹配，否则无解。
        - B的格式：EABCD-EABCD-EABCD-EA
        - A循环4次：ABCD-[EABCD-EABCD-EABCD-EA]-BCDE
        可以试着证明一下，然后用下面的公式计算limit。
        */
        int ret = -1;
        if (A.length() > 0) {
            int limit = B.length() / A.length();
            if ((B.length() % A.length()) <= 1) {
                ++limit;
            } else {
                limit += 2;
            }
            ret = 1;
            StringBuilder sb = new StringBuilder();
            sb.append(A);
            while (limit > 0) {
                if (sb.length() >= B.length()) {
                    for (int i = 0; i < sb.length() - B.length() + 1; ++i) {
                        int j = 0;
                        while (j < B.length()) {
                            if (sb.charAt(i + j) != B.charAt(j)) {
                                break;
                            } else {
                                ++j;
                            }
                        }
                        if (j == B.length()) {
                            return ret;
                        }
                    }
                }
                sb.append(A);
                ++ret;
                --limit;
            }
        }
        return ret;
    }
}